package LeetCode;

class LinkedNode {
    int val;
    LinkedNode next;

    LinkedNode(int x) {
        val = x;
    }
}

public class Code19_removeNthFromEnd {

//    19. 删除链表的倒数第 N 个结点
//    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//    输入：head = [1,2,3,4,5], n = 2
//    输出：[1,2,3,5]
//    解释：删除了链表的倒数第2个结点，即值为4的结点。
    public LinkedNode removeNthFromEnd(LinkedNode head, int n) {
        // 检查头结点是否为空，为空则直接返回null
        if (head == null) {
            return null;
        }
        // 创建一个虚拟头结点，简化边界条件的处理
        LinkedNode dummy = new LinkedNode(0);
        dummy.next = head;
        // 初始化两个指针p1和p2，都指向虚拟头结点
        LinkedNode p1 = dummy;
        LinkedNode p2 = dummy;
        // 移动p1指针，使其与p2指针之间相隔n个结点
        while (n >= 0) {
            p1 = p1.next;
            n--;
        }
        // 同时移动p1和p2指针，直到p1指针到达链表末尾
        // 此时p2指针指向的是倒数第n个结点的前一个结点
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 跳过倒数第n个结点，将其从链表中删除
        p1.next = p1.next.next;
        // 返回删除结点后的链表头结点
        return dummy.next;
    }

}
